#ifndef _basic_queue_hpp_
#define _basic_queue_hpp_

/** \file basic_queue.hpp
 *  \author Adrian Schweizer
 *  \created  $Sa 18 Aug 03:48:01 pm CEST 2007 schwadri@SchwadriComp.local$
 *  \modified $Mo 27 Aug 05:27:14 pm CEST 2007 schwadri@SchwadriComp.local$
 */

#include <memory>

namespace core {

    namespace detail {
        //forward decl of implementation
        template<class T,class A>
            class   basic_queue_impl;
    }

    /** \brief A queue with an additional vector interface. STL compatible.
     *
     *  A \p basic_queue is a \a queue with some additional interface elements of a \a vector. It provides constant time insertion
     *  of elements at the back, constant time removal at the front and constant time random access. Memory management is done
     *  through an \a allocator policy.
     *
     *  \par Template Parameters
     *  - \p T         The queue's \a value_type: the type of object that is stored in the queue.<br>
     *                 Must be \a copyconstructible and \a assignable
     *  - \p Allocator The queue's \a allocator, used for all internal memory management. Any
     *                 STL compliant allocator may be used. This parameter is \a optional and \a defaults to
     *                 \a std::allocator<T>.
     *
     *  \par Iterator Invalidation
     *  Element insertion (calls to \a push(), \a push_back() ) , removal ( \a pop(), \a pop_front() ) and calls
     *  to \a resize() may invalidate any iterator associated with the \a basic_queue in question.
     *
     *  \par Example
     *  \code
     *  core::basic_queue<int>  q;
     *  q.push(9);
     *  assert(q.size() == 1 && q.capacity() >= 1 && !q.empty() && q.front() == 9 && q[0] == 9);
     *  q.pop();
     *  \endcode
     *  \warning There are yet some unresolved issues regarding exception safety. While exception safety of the internal state of the container
     *  is guaranteed, already constructed elements will not be destructed upon an exception during the copy constructor or reallocation. As
     *  long as the contained elements do not allocate memory by themselves or change state of an external object during construction this should
     *  be not a problem. If they do, a throwing constructor could lead to memory leakage.
     */
    template<class T, class Allocator=std::allocator<T> >
        class   basic_queue
        {
            typedef basic_queue<T,Allocator>                my_type;
            typedef detail::basic_queue_impl<T,Allocator>   impl_type;
            typedef typename impl_type::allocator_type      allocator_type;
        public:
            typedef typename impl_type::size_type           size_type;          ///<An unsigned integral type
            typedef typename impl_type::pointer             pointer;            ///<Pointer to \p T
            typedef typename impl_type::const_pointer       const_pointer;      ///<Const Pointer to \p T
            typedef typename impl_type::reference           reference;          ///<Reference to \p T
            typedef typename impl_type::const_reference     const_reference;    ///<Const Reference to \p T
            typedef typename impl_type::value_type          value_type;         ///<The type of object, \p T, stored in the \a queue
            typedef typename impl_type::iterator            iterator;           ///<Iterator used to iterate through a \a queue
            typedef typename impl_type::const_iterator      const_iterator;     ///<Const Iterator used to iterate through a \a queue

            /** \brief creates an empty \a queue and allocates space to hold at least \a size elements
             */
            basic_queue(size_type size)
            :   m_impl(size)
            { }

            /** \brief creates an empty \a queue*/
            basic_queue()
            :   m_impl()
            { }

            /** \brief copy construct a basic_queue from another queue containing the same type of objects
             */
            basic_queue(const my_type& other)
            :   m_impl(other.m_impl)
            { }

            /** \brief default dtor
             *
             *  All elements in the \p basic_queue are destroyed
             */
            ~basic_queue()
            { }

            /** \brief return the maximum number of elements a basic_queue could hold theoretically (if there was enough ram)*/
            inline size_type max_size() const
            {
                return m_impl.max_size();
            }

            /** \brief get the number of elements that can be pushed into the queue before more additional space has to be allocated
             */
            inline size_type capacity() const
            {
                return m_impl.capacity();
            }

            /** \brief returns the number of elements currently contained
             */
            inline size_type size() const
            {
                return m_impl.size();
            }
            /** \brief this is the same as capacity() == size()
             */
            inline bool    full() const
            {
                return m_impl.full();
            }

            /** \brief returns true if the container is empty.
             *
             *  This is faster than
             *  \code
             *  size()==0
             *  \endcode
             */
            inline bool    empty() const
            {
                return m_impl.empty();
            }

            /**  \brief clears the container of all elements
             *
             *  If the contained elements have a nontrivial destructor, it will be called
             *  for each element.
             */
            void    clear()
            {
                m_impl.clear();
            }

            /** \brief reserve space for more elements
             *
             *  If \a n is less than or equal to \a capacity(), this call has no effect. Otherwise, it is a request
             *  for allocation of additional memory. If the request is successful, then \a capacity() is greater
             *  than or equal to \a n. otherwise, \a capacity() is unchanged. In either case, \a size() is unchanged.
             *  \param[in]  n   How much space to reserve. Number of elements.
             */
            void    reserve(size_type  n)
            {
                m_impl.reserve(n);
            }

            /** \brief resize the container
             *
             *  If \a size > current size, this operation reserves more space for elements and constructs
             *  additional elements initializing them with \a value.
             *  \warning If \a size < current the operation outcome is undefined. this method has quite some issues so
             *  its best NOT to use it if you don't know exactly what you are doing
             */
            void    resize(size_type size, const_reference value=value_type())
            {
                m_impl.resize(size,value);
            }

            /** \brief push back a value into the container
             *
             *  A copy of the supplied value is pushed back at the end of the queue.
             */
            reference    push(const_reference value)
            {
                return m_impl.push(value);
            }

            /** \brief pop a value of the front
             *
             *  \note If the queue is empty, this does nothing
             */
            void    pop()
            {
                m_impl.pop();
            }

            /** \brief push back a value into the container
             *
             *  \sa push
             */
            inline void    push_back(const_reference value)
            {
                m_impl.push_back(value);
            }

            /** \brief pop a value of the front
             *
             *  \sa pop
             */
            inline void     pop_front()
            {
                m_impl.pop_front();
            }

            /** \brief Returns a reference to the element at the front
             *
             *  \warning The behaviour is undefined if the queue is empty!
             */
            inline reference       front()         { return m_impl.front(); }

            /** \brief Returns a const reference to the element at the front
             *
             *  \warning The behaviour is undefined if the queue is empty!
             */
            inline const_reference front() const   { return m_impl.front(); }

            /** \brief Returns a const reference to the element at the back
             *
             *  \warning The behaviour is undefined if the queue is empty!
             */
            inline const_reference back() const   { return m_impl.back(); }

            /** \brief Returns a reference to the element at the back
             *
             *  \warning The behaviour is undefined if the queue is empty!
             */
            inline reference       back()         { return m_impl.back(); }

            /** \brief Returns a const reference to the element at position \a index
             *
             *  \param[in] index    where \f$ index \in \left[0,size() \right)\f$. if \a index
             *                      is outside this valid range behaviour is undefined.
             */
            inline const_reference  operator[](size_type index) const   { return m_impl[index]; }

            /** \brief Returns a const reference to the element at position \a index
             *
             *  \param[in] index    where \f$ index \in \left[0,size() \right)\f$. if \a index
             *                      is outside this valid range behaviour is undefined.
             */
            inline reference        operator[](size_type index)         { return m_impl[index]; }

            /** \name Iterator Methods */ //@{
            /** \brief Returns a const iterator pointing to the first element in the container*/
            inline const_iterator begin() const
            {
                return  m_impl.begin();
            }

            /** \brief Returns const iterator pointing one past the last element in the container*/
            inline const_iterator end() const
            {
                return  m_impl.end();
            }

            /** \brief Returns an iterator pointing to the first element in the container*/
            inline iterator begin()
            {
                return  m_impl.begin();
            }

            /** \brief Returns iterator pointing one past the last element in the container*/
            inline iterator end()
            {
                return  m_impl.end();
            }
            //@}

            /** \brief swaps the content of two \a basic_queue's*/
            void swap(my_type& o)
            {
                m_impl.swap(o.m_impl);
            }
        private:
            impl_type   m_impl; //implementation
        };

    /** \internal
     *  \brief specialization of the swap routine for this container
     */
    template<class T, class A>
        void swap(basic_queue<T,A>& q1, basic_queue<T,A>& q2)
        {
            q1.swap(q2);
        }

} // namespace core

#include "detail/basic_queue_impl.hpp"

#endif // _basic_queue_hpp_
